/*
 *https://leetcode.cn/problems/find-if-path-exists-in-graph/
 *1971. 寻找图中是否存在路径
 *easy 吴朝泽 2024.9.25
 *并查集
 模板题，因为本题求的只是判断两点之间是否具有连通性，不用求两个点之间具体的操作，故套用模板创一个对象调用函数即可
*/

class union_find {
public:
    // 构造从 0 到 n - 1 的节点
    union_find(int n) : n(n) {
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }
    // 合并两个节点
    void pair(int index1, int index2) {
        parent[find(index2)] = find(index1);
    }
    // 找到根节点
    int find(int index) {       // 递归函数，找根节点的同时进行路径压缩
        if (parent[index] != index) {
            parent[index] = find(parent[index]);
        }
        return parent[index];
    }
    // 判断连接性
    bool check(int index1, int index2) {
        return find(index1) == find(index2);
    }
    // 返回连通图的数量
    int groupCount() {      // 集合去重得到连通图的数量
        unordered_set<int> us;
        for (int i = 0; i < n; ++i) us.emplace(find(i));
        return us.size();
    } 
private:
    int *parent, n;
};

class Solution {
public:
    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
        union_find uf(n);

        for(auto& k : edges)
            path.pair(k[0] , k[1]);

        return path.check(source,destination);
    }
};